package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/merge-two-sorted-lists/">合并两个有序链表 [简单]</a>
 * 将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。
 * input: l1=[1,2,4],l2=[1,3,4] -> output:[1,1,2,3,4,4]
 * 边界：
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 *
 * @author zhenzicheng
 * @date: 2022-06-01 11:07
 */
public class MergeTwoSortedLists_21 {

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 边界
    if (list1 == null) {
      return list2;
    }
    if (list2 == null) {
      return list1;
    }
    // 新的头结点，实际头结点应为head.next
    ListNode head = new ListNode(0);
    ListNode tail = head; // 幽灵尾节点
    // 循环遍历
    while (list1 != null && list2 != null) {
      if (list1.val <= list2.val) {
        tail.next = list1;
        list1 = list1.next;
      } else {
        tail.next = list2;
        list2 = list2.next;
      }
      tail = tail.next;
    }
    // 判断完毕后还需要判断哪个链表没有遍历完，如果存在没有遍历完的数据直接用最后一个节点直接指向剩余节点
    if (list1 == null) {
      tail.next = list2;
    }
    if (list2 == null) {
      tail.next = list1;
    }

    return head.next;
  }

}
